U.S. Pat. No. 7,406,197, issued Jul. 29, 2008 to Francos et al., and U.S. Pat. No. 786,502, issued Jan. 4, 2011 to Francos et al., the entire contents of each which is incorporated herein by reference, are addressed to a parametric estimation of multi-dimensional homeomorphic transformations. U.S. Pat. No. 8,275,204, issued Sep. 25, 2012 to Kovalsky et al., the entire contents of which are incorporated herein by reference, is addressed to an estimation of joint radiometric and geometric image deformations.
Analyzing and understanding different appearances of an object is an elementary problem in various fields. Since acquisition conditions vary (e.g., pose, illumination), the set of possible observations on a particular object is immense. We consider a problem where, in general, we are given a set of observations (for example, images) of different objects, each undergoing different geometric and radiometric deformations. As a result of the action of the deformations, the set of different realizations of each object is generally a manifold in the space of observations. Therefore, the detection and recognition problems are strongly related to the problems of manifold learning and dimensionality reduction of high dimensional data that have attracted considerable interest in recent years, see e.g., “Special Issue on Dimensionality Reduction Methods,” Signal Process. Mag., issued March 2011, the entire contents of which are incorporated herein by reference. The common underlying idea unifying existing manifold learning approaches is that although the data is sampled and presented in a high-dimensional space, for example because of the high resolution of the camera sensing the scene, in fact the intrinsic complexity and dimensionality of the observed physical phenomenon is very low.
The problem of characterizing the manifold created by the multiplicity of appearances of a single object in some general setting is studied intensively in the field of non-linear dimensionality reduction. As indicated in “Unsupervised Learning of Image Manifolds by Semidefinite Programming”, by K. Weinberger and L. Saul, published in Int. J. Comput. Vision, pp. 77-90, 2006, the entire contents of which are incorporated herein by reference, linear methods for dimensionality reduction such as PCA and MDS generate faithful projections when the observations are mainly confined to a single low dimensional linear subspace, while they fail in case the inputs lie on a low dimensional non-linear manifold. Hence, a common approach among existing non-linear dimensionality reduction methods is to expand the principles of the linear spectral methods to low-dimensional structures that are more complex than a single linear subspace. This is achieved, for example, by assuming the existence of a smooth and invertible locally isometric mapping from the original manifold to some other manifold which lies in a lower dimensional space, as described in: “Learning to Traverse Image Manifolds”, by P. Dollar, V. Rabaud and S. Belongie, published in Proc. NIPS, 2006; “A Global Geometric Framework for Nonlinear Dimensionality Reduction”, by J. B. Tenenbaum, V. de Silva and J. C. Langford, published in Science, vol. 290, pp. 2319-2323, 2000; and “Nonlinear Dimensionality Reduction by Locally Linear Embedding”, by S. T. Roweis and L. K. Saul, published in Science, vol. 290, pp. 2323-2326, 2000, the entire contents of each of with are incorporated herein by reference.
An additional family of widely adopted methods aims at piecewise approximating the manifold or a set of manifolds, as a union of linear subspaces, in what is known as the subspace clustering problem, as described in: “Estimation of subspace arrangements with applications in modeling and segmenting mixed data”, by Y. Ma, A. Yang, H. Derksen, and R. Fossum, published in SIAM Rev., vol. 50, no. 3, pp. 413-458, 2008; and “Subspace Clustering”, by R. Vidal, published in Signal Process. Mag., pp. 52-67, March 2011, the entire contents of each of which are incorporated herein by reference. The challenge here is to simultaneously cluster the data into multiple linear subspaces and to fit a low-dimensional linear subspace to each set of observations. A different assumption, namely that the data has a sufficiently sparse representation as a linear combination of the elements of an a-priori known basis or of an over-complete dictionary, as described in: “Greed is good: Algorithmic results for sparse approximation”, by J. Tropp, published in IEEE Trans. Info. Theory, vol. 50, no. 10, pp. 2231-2242, 2004; and “Dictionary Learning”, by I. Tosic and P. Frossard, published in Signal Process. Mag., pp. 27-38, March 2011, the entire contents of each of which is incorporated herein by reference. This leads to the framework of linear dictionary approximations of the manifolds. Geometrically, this assumption implies that the manifold can be well approximated by its tangent plane, with the quality of this approximation depending on the local curvature of the manifold.
Indeed, there are many cases where no prior knowledge on the reasons for the variability in the appearances of an object is available. On the other hand, there are many scenarios in which such information is inherently available, and hence can be efficiently exploited.
Typically, to compare different images, point matching algorithms and/or or global registration algorithms are utilized. Point matching algorithms aim at finding key points in the observed image and characterize them through the properties of small regions around them. These inherently local approaches use relatively small amounts of information (small patches) in generating the descriptor of a key point. As a consequence they frequently result in ambiguous descriptors, which in turn lead to high rates of false matches that need to be eliminated before any further processing can take place. Such verification procedures require knowledge of the global geometric transformation model (e.g., RANS AC) and are computationally demanding. Moreover, such global geometric transformation model is often unknown, or difficult to estimate. On the other end, global registration algorithms may be applied only when the family of expected geometric deformations is a-priori known, and the radiometric deformations between the two observations are minimal.